%!Tex Program = xelatex
\documentclass[a4paper,12pt]{article}
\usepackage{amssymb,amsmath,amsfonts,amsthm}
%\usepackage{newtxtext,newtxmath}
\usepackage{fontspec,xunicode,xltxtra}
\usepackage[english]{babel}
\usepackage{listings}
\usepackage{mathrsfs}
%\usepackage{zhfontcfg}
%\usepackage{indentfirst}
%\usepackage[colorlinks,linkcolor=black]{hyperref}
%\usepackage{setspace}
%\usepackage{geometry}
% or whatever

%\usepackage[latin1]{inputenc}
% or whatever

\XeTeXlinebreaklocale "zh"
\XeTeXlinebreakskip = 0pt plus 1pt minus 0.1pt

% Ubuntu
%\newfontfamily\hei{WenQuanYi Zen Hei Mono}
%%\newfontfamily\whei{STHeitiSC-Medium}
%\newfontfamily\kaishu{AR PL KaitiM GB}
%\newfontfamily\song{AR PL SungtiL GB}
%%\newfontfamily\lishu{STLibianSC-Regular}
%\setmainfont[Mapping=tex-text]{AR PL SungtiL GB}
%\setsansfont[Mapping=tex-text]{AR PL KaitiM GB}
%\setmonofont[Mapping=tex-text]{WenQuanYi Zen Hei Mono}

% Mac
\newfontfamily\hei{STHeitiSC-Light}
\newfontfamily\whei{STHeitiSC-Medium}
\newfontfamily\kaishu{STKaitiSC-Regular}
\newfontfamily\song{STSongti-SC-Regular}
\newfontfamily\lishu{STLibianSC-Regular}
\setmainfont[Mapping=tex-text]{STSongti-SC-Regular}
\setsansfont[Mapping=tex-text]{STKaitiSC-Regular}
\setmonofont[Mapping=tex-text]{STHeitiSC-Medium}
\renewcommand{\baselinestretch}{1.25}

\usepackage{fancyhdr}
\usepackage{lastpage}
\usepackage{ulem}
\usepackage{pgf}
\usepackage{graphicx}

\usepackage[hmargin={3.18cm, 3.18cm}, width=14.64cm,
             vmargin={2.54cm, 2.54cm}, height=24.62cm]{geometry}
\pagestyle{empty}

\usepackage{fancyhdr}
\usepackage{lastpage}
\pagestyle{fancy} %fancyhdr宏包新增的页面风格
\renewcommand{\headrulewidth}{0pt}
%\fancyhf{}
\cfoot{第 \thepage 页，共 \pageref{LastPage} 页}%当前页 of 总页数

\renewcommand\baselinestretch{1.2}
\setlength{\headwidth}{\textwidth}

%\renewcommand{\labelenumi}{\bf{\chinese{enumi}、}}
\renewcommand{\labelenumii}{\arabic{enumii}.}
\renewcommand{\labelenumiii}{\Roman{enumiii}}

\newcommand{\chuhao}{\fontsize{42pt}{\baselineskip}\selectfont} % 字号设置
\newcommand{\xiaochuhao}{\fontsize{36pt}{\baselineskip}\selectfont} % 字号设置
\newcommand{\yihao}{\fontsize{28pt}{\baselineskip}\selectfont} % 字号设置
\newcommand{\erhao}{\fontsize{21pt}{\baselineskip}\selectfont} % 字号设置
\newcommand{\xiaoerhao}{\fontsize{18pt}{\baselineskip}\selectfont} % 字号设置
\newcommand{\sanhao}{\fontsize{15.75pt}{\baselineskip}\selectfont} % 字号设置
\newcommand{\sihao}{\fontsize{14pt}{\baselineskip}\selectfont} % 字号设置
\newcommand{\xiaosihao}{\fontsize{12pt}{\baselineskip}\selectfont} % 字号设置
\newcommand{\wuhao}{\fontsize{10.5pt}{\baselineskip}\selectfont} % 字号设置
\newcommand{\xiaowuhao}{\fontsize{9pt}{\baselineskip}\selectfont} % 字号设置
\newcommand{\liuhao}{\fontsize{7.875pt}{\baselineskip}\selectfont} % 字号设置
\newcommand{\qihao}{\fontsize{5.25pt}{\baselineskip}\selectfont} % 字号设置

\newtheorem{theorem}{定理}
\newtheorem{definition}{定义}
\addto{\captionsenglish}{%
  \renewcommand{\refname}{参考文献}%
  \renewcommand{\proofname}{证明}%
  \renewcommand{\figurename}{图}%
%  \renewcommand{\bibname}{参考文献}%
}

\renewcommand{\theequation}{\arabic{section}.\arabic{equation}}
\renewcommand{\thetheorem}{\arabic{section}.\arabic{theorem}}
\renewcommand{\thedefinition}{\arabic{section}.\arabic{definition}}


\begin{document}

\title{\hei 插入排序的平均时间效率测试}

\author{王何宇 \thanks{email: wangheyu@zju.edu.cn}\\
        数学科学学院，数学与应用数学专业\\
        学号：9401???
       }
%\date{}
\maketitle

%%------------------------------------------
\section{问题}
\setcounter{equation}{0}
\setcounter{theorem}{0}
\setcounter{definition}{0}

通过实际数值算例，统计并验证插入排序在平均意义下的相对时间效率是
$$
t_n = \Theta(n),
$$
其中，$n$ 表示问题的输入规模，在本例中，即指输入的待排序数组的长度；
$t_n$ 表示对一个输入规模为 $n$ 的插入排序过程所耗费的实际时间。
对问题和算法的详细描述，参见 \cite{Cormen2009}。

\section{实验方案}
\setcounter{equation}{0}
\setcounter{theorem}{0}
\setcounter{definition}{0}

测试运行环境为虚拟机 Virtual Box 下的 Ubuntu 16.04。由于测试的是相对时间效率，
因此对具体的机器性能不敏感，这里不再列出更多配置细节。

\subsection{项目文件说明}
程序采用 2011 标准的 C++ 编写，项目名称为 \verb|InsertionSort|，项目文件结构如下：
\begin{verbatim}
InserttionSort
    |---C_style  
    |---generate_data  
    |---stat  
    |---timer  
    |---vector
\end{verbatim}
其中，
\begin{itemize}
\item \verb|C_style| 为一个标准 C 风格的实现；
\item \verb|generate_data| 能自动产生指定长度供排序测试的随机整数数组，
并采用 C++11 提供的 random 库确保随机性。其中随机数种子采用对一个具体程序过程的实时统计得到，
而时间计算则调用了 C++11 提供的 chrono 库，精度到纳秒（$10^{-9}$秒）；
\item \verb|stat| 用于对批量产生时间数据的统计，目前只实现了多次重复测试的平均时间计算；
\item \verb|timer| 提供计算一个具体排序运行时间的程序和脚本。其中 \verb|main.cpp| 
用于实际时间计算，同样通过 chrono 库完成；Bash 脚本 \verb|batch_test| 共有 4 个用户参数，
依次分别代表：
\begin{itemize}
\item \$1 测试总组数
\item \$2 测试的起始数组长度
\item \$3 每组测试的增量
\item \$4 每组测试的重复次数
\end{itemize}
专门用于测试排序的相对时间效率。而脚本 \verb|test4matlab| 功能与参数设置和 \verb|batch_test|
一致，区别在于其输出为一个 Matlab 脚本文件的格式；
\item \verb|vector| 为一个 C++ STL 风格的实现，其中 InsertionSort 被单独写成一个函数 
\verb|InsertionSort|，便于精确计算排序时间。本实验实际测试的是这一版本的程序。
\end{itemize}

\subsection{实验步骤}
\begin{enumerate}
\item 在 \verb|timer| 目录下执行：
\begin{verbatim}
./test4matlab 20 20 20 100 > result.m
\end{verbatim}
产生 $20$ 组数组长度从 $20$ 以等量 $20$ 递增到 $400$，每组重复测试 $100$ 次，每一次的输入数组均重新抽取。
并将结果重定向为 Matlab 脚本文件 result.m；
\item 在 Matlab 或 octave 中执行 result.m 脚本，观察图像行为；
\item 在 Matlab 中运行：
\begin{verbatim}
plot(re(:, 1), re(:, 2)./re(:, 1).^2,'.', 'MarkerSize', 20);
xlabel('Problem Size: n');
ylabel('Time Efficiency: t_n / n^2');
set(gca,'FontSize',40); 
\end{verbatim}
以观察 $\frac{t_n}{n^2}$ 的极限行为，并将结果调整为便于输出的图像。
\item 分析数据，得出结论并撰写报告。
\end{enumerate}

\section{数值结果}
\setcounter{equation}{0}
\setcounter{theorem}{0}
\setcounter{definition}{0}
实验结果见图 \ref{fig::re_tn_n2}。从 $t_n / n^2$ 的增长趋势可以看出，
随着 $n$ 增大，$t_n / n^2$ 逐渐趋于一常数，这一现象与理论结果：
$$
t_n = \Theta(n^2)
$$
一致。

\begin{figure}[!htbp]
\centering
\includegraphics[width=0.7\textwidth]{../images/re_nice.png}
\caption{插入排序对于随机分布整数数组的时间效率，这里每一个点代表一组重复了 $100$ 次后取平均的实验结果。
  共 $20$ 组，输入数组的规模从长度 $20$ 起，等量递增到 $400$。每一次重复实验均做了新抽取。}
\label{fig::re_tn_n2}
\end{figure}

\section{结论}
\setcounter{equation}{0}
\setcounter{theorem}{0}
\setcounter{definition}{0}
实验结果验证了理论结果：插入排序的平均时间效率是 $t_n = \Theta(n)$。

\bibliographystyle{plain}
\bibliography{../crazyfish}
\end{document}
